#include "filesys/inode.h"
#include <list.h>
#include <debug.h>
#include <round.h>
#include <stdio.h>
#include <string.h>
#include "filesys/filesys.h"
#include "filesys/free-map.h"
#include "threads/malloc.h"
#include "threads/synch.h"

/* Identifies an inode. */
#define INODE_MAGIC 0x494e4f44

/* On-disk inode.
   Must be exactly DISK_SECTOR_SIZE bytes long. */
struct inode_disk
  {
    disk_sector_t start;                /* First data sector. */
    off_t length;                       /* File size in bytes. */
    unsigned magic;                     /* Magic number. */
    uint32_t idx[125];                  /* Not used. */
  };

struct indirect_b
  {
    uint32_t index[128];                  /* Index of indirect blocks */
  };

/* Returns the number of sectors to allocate for an inode SIZE
   bytes long. */
static inline size_t
bytes_to_sectors (off_t size)
{
  return DIV_ROUND_UP (size, DISK_SECTOR_SIZE);
}

/* In-memory inode. */
struct inode 
  {
    struct list_elem elem;              /* Element in inode list. */
    disk_sector_t sector;               /* Sector number of disk location. */
    int open_cnt;                       /* Number of openers. */
    bool removed;                       /* True if deleted, false otherwise. */
    int deny_write_cnt;                 /* 0: writes ok, >0: deny writes. */
    struct inode_disk data;             /* Inode content. */
    
    struct indirect_b *idx_cache[130];  /* A cache for the sector we are going to use in disk*/
    
    bool write_inode;                   /* It helps us to know if this inode has changed */
    
    bool write[130];                    /* It will tell us if the corresponding entry in idx_cache has been modified */
    
    struct lock lock_idx;               /* The lock we use for our indices */
    struct lock read_write;               /* The lock we use extending files */
  };

static disk_sector_t get_sector_from_index(struct inode *inode, off_t index);

static disk_sector_t allocate_sector_in_index(struct inode *inode, off_t index);

static void init_sector(disk_sector_t sector);

static void init_indirect(struct indirect_b * ind_block);

/* Returns the disk sector that contains byte offset POS within
   INODE.
   Returns -1 if INODE does not contain data for a byte at offset
   POS. */
static disk_sector_t
byte_to_sector (struct inode *inode, off_t pos) 
{
  ASSERT (inode != NULL);

  disk_sector_t r;
  if(inode->sector == FREE_MAP_SECTOR){
    if(pos < inode->data.length)
      r = inode->data.start + pos / DISK_SECTOR_SIZE;
    else
      r = -1;
  } else {
    off_t  idx = pos / DISK_SECTOR_SIZE;
    lock_acquire(&inode->lock_idx);
    r = get_sector_from_index(inode, idx);
    lock_release(&inode->lock_idx);
  }
  return r;
  //if (pos < inode->data.length){
  //}
  /*else
    return -1;*/
}

/* List of open inodes, so that opening a single inode twice
   returns the same `struct inode'. */
static struct list open_inodes;

/* Initializes the inode module. */
void
inode_init (void) 
{
  list_init (&open_inodes);
}

/* Initializes an inode with LENGTH bytes of data and
   writes the new inode to sector SECTOR on the file system
   disk.
   Returns true if successful.
   Returns false if memory or disk allocation fails. */
bool
inode_create (disk_sector_t sector, off_t length)
{
  struct inode_disk *disk_inode = NULL;
  bool success = false;

  ASSERT (length >= 0);

  /* If this assertion fails, the inode structure is not exactly
     one sector in size, and you should fix that. */
  ASSERT (sizeof *disk_inode == DISK_SECTOR_SIZE);

  disk_inode = calloc (1, sizeof *disk_inode);
  if (disk_inode != NULL)
    {
      size_t sectors = bytes_to_sectors (length);
      disk_inode->length = length;
      disk_inode->magic = INODE_MAGIC;

      int k;
      for(k = 0; k < 125; k++)
	disk_inode->idx[k] = -1;


      if(sector == FREE_MAP_SECTOR){
	if (free_map_allocate (sectors, &disk_inode->start))
	  {
	    disk_write (filesys_disk, sector, disk_inode);
	    if (sectors > 0) 
	      {
		static char zeros[DISK_SECTOR_SIZE];
		size_t i;
              
		for (i = 0; i < sectors; i++) 
		  disk_write (filesys_disk, disk_inode->start + i, zeros); 
	      }
	    success = true; 
	  }
      } else {
	disk_write (filesys_disk, sector, disk_inode);
	success = true; 
      }
      free (disk_inode);
    }
  return success;
}

/* Reads an inode from SECTOR
   and returns a `struct inode' that contains it.
   Returns a null pointer if memory allocation fails. */
struct inode *
inode_open (disk_sector_t sector) 
{
  struct list_elem *e;
  struct inode *inode;

  /* Check whether this inode is already open. */
  for (e = list_begin (&open_inodes); e != list_end (&open_inodes);
       e = list_next (e)) 
    {
      inode = list_entry (e, struct inode, elem);
      if (inode->sector == sector) 
        {
          inode_reopen (inode);
          return inode; 
        }
    }

  /* Allocate memory. */
  inode = malloc (sizeof *inode);
  if (inode == NULL)
    return NULL;

  /* Initialize. */
  list_push_front (&open_inodes, &inode->elem);
  inode->sector = sector;
  inode->open_cnt = 1;
  inode->deny_write_cnt = 0;
  inode->removed = false;
  inode->write_inode = false;
  disk_read (filesys_disk, inode->sector, &inode->data);
  int i;

  lock_init(&inode->lock_idx);
  lock_init(&inode->read_write);

  for(i = 0; i < 130; i++){
    inode->idx_cache[i] = NULL;
    inode->write[i] = false;
  }
  
  return inode;
}

/* Reopens and returns INODE. */
struct inode *
inode_reopen (struct inode *inode)
{
  if (inode != NULL)
    inode->open_cnt++;
  return inode;
}

/* Returns INODE's inode number. */
disk_sector_t
inode_get_inumber (const struct inode *inode)
{
  return inode->sector;
}

/* Closes INODE and writes it to disk.
   If this was the last reference to INODE, frees its memory.
   If INODE was also a removed inode, frees its blocks. */
void
inode_close (struct inode *inode) 
{
  /* Ignore null pointer. */
  if (inode == NULL)
    return;
  
  bool b = inode->sector == FREE_MAP_SECTOR;
  /* Release resources if this was the last opener. */
  if (--inode->open_cnt == 0)
    {
      /* Remove from inode list and release lock. */
      list_remove (&inode->elem);
 
      /* Deallocate blocks if removed. */
      if (inode->removed) 
        {
          free_map_release (inode->sector, 1);
	        if(b)
	          {
	            free_map_release (inode->data.start,
			              bytes_to_sectors (inode->data.length)); 
	          } 
	        else 
	          {
	            // Release each of the sector used
	            int i = 0;
	            off_t size = inode_length(inode);
	            disk_sector_t sec;
	            // Release all sectors assigned to this file
	            while(i < (size/DISK_SECTOR_SIZE) && i < 16635){
	              lock_acquire(&inode->lock_idx);
	              sec = get_sector_from_index(inode, i++);
	              lock_release(&inode->lock_idx);
	              if(sec != (uint32_t)-1)
		              free_map_release (sec, 1);
	            }

	            if(inode->idx_cache[0] != NULL)
	              free(inode->idx_cache[0]);
	            if(inode->idx_cache[1] != NULL)
	              free(inode->idx_cache[1]);
	            
	            for(i = 2; i < 130; i++)
	              if(inode->idx_cache[i] != NULL)
		              free(inode->idx_cache[i]);
	            
	            free (inode);
	            return;
	        }
	      }
	      
      if(!b)
        {
	        // Copy inode data in disk in case it changed
	        //if(inode->write_inode)
	          disk_write(filesys_disk, inode->sector, &inode->data);
	        int j;

	        for(j = 0; j < 130; j++)
	          {
	            if(inode->write[j])
	              {
	                if(j == 0)
	                  disk_write(filesys_disk, inode->data.idx[123],(uint8_t *) inode->idx_cache[0]);
	                else if(j == 1)
	                  disk_write(filesys_disk, inode->data.idx[124], (uint8_t *)inode->idx_cache[1]);
	                else
	                  disk_write(filesys_disk, inode->idx_cache[1]->index[j-2], (uint8_t *)inode->idx_cache[j]);
	              }

              //We can't free idx_cache[1] because we may use it later on, e.g. inode->idx_cache[1]->index[*]
	            if(inode->idx_cache[j] != NULL && j != 1)
	              free(inode->idx_cache[j]);
	          }

          if(inode->idx_cache[1] != NULL)
            free(inode->idx_cache[1]);
        }
      free (inode); 
    }
}

/* Marks INODE to be deleted when it is closed by the last caller who
   has it open. */
void
inode_remove (struct inode *inode) 
{
  ASSERT (inode != NULL);
  inode->removed = true;
}

/* Reads SIZE bytes from INODE into BUFFER, starting at position OFFSET.
   Returns the number of bytes actually read, which may be less
   than SIZE if an error occurs or end of file is reached. */
off_t
inode_read_at (struct inode *inode, void *buffer_, off_t size, off_t offset) 
{
  uint8_t *buffer = buffer_;
  off_t bytes_read = 0;
  uint8_t *bounce = NULL;

  while (size > 0) 
    {
      /* Disk sector to read, starting byte offset within sector. */
      disk_sector_t sector_idx = byte_to_sector (inode, offset);

      int sector_ofs = offset % DISK_SECTOR_SIZE;

      /* When the file needs to be extended we lock this process */
      bool extend = sector_idx == (uint32_t)-1;
      if(extend)
	lock_acquire(&inode->read_write);


      /* Bytes left in inode, bytes left in sector, lesser of the two. */
      off_t inode_left = inode_length (inode) - offset;
      int sector_left = DISK_SECTOR_SIZE - sector_ofs;
      int min_left = inode_left < sector_left ? inode_left : sector_left;

      /* Number of bytes to actually copy out of this sector. */
      int chunk_size = size < min_left ? size : min_left;
      /* We assure that the offset is less than inode's length*/
      if (chunk_size <= 0){
	if(extend)
	  lock_release(&inode->read_write);
        break;
      }

      if (sector_ofs == 0 && chunk_size == DISK_SECTOR_SIZE) 
        {
          /* Read full sector directly into caller's buffer. */
	  if(sector_idx == (uint32_t)-1 && inode->sector != FREE_MAP_SECTOR){
	    memset(buffer + bytes_read, 0, DISK_SECTOR_SIZE);
	  }
	  else{
	    disk_read (filesys_disk, sector_idx, buffer + bytes_read); 
	  }
        }
      else 
        {
          /* Read sector into bounce buffer, then partially copy
             into caller's buffer. */
          if (bounce == NULL) 
            {
              bounce = malloc (DISK_SECTOR_SIZE);
              if (bounce == NULL){
		if(extend)
		  lock_release(&inode->read_write);
                break;
	      }
            }

	  if(sector_idx == (uint32_t)-1 && inode->sector != FREE_MAP_SECTOR){
	    memset(buffer + bytes_read, 0, chunk_size);
	  } else {
	    disk_read (filesys_disk, sector_idx, bounce);
	    memcpy (buffer + bytes_read, bounce + sector_ofs, chunk_size);
	  }
        }
      
      /* Advance. */
      size -= chunk_size;
      offset += chunk_size;
      bytes_read += chunk_size;

      if(extend)
	lock_release(&inode->read_write);
    }
  free (bounce);

  return bytes_read;
}






/* Writes SIZE bytes from BUFFER into INODE, starting at OFFSET.
   Returns the number of bytes actually written, which may be
   less than SIZE if end of file is reached or an error occurs.
   (Normally a write at end of file would extend the inode, but
   growth is not yet implemented.) */
off_t
inode_write_at (struct inode *inode, const void *buffer_, off_t size,
                off_t offset) 
{
  const uint8_t *buffer = buffer_;
  off_t bytes_written = 0;
  uint8_t *bounce = NULL;
  bool ok = inode->sector != FREE_MAP_SECTOR;

  if (inode->deny_write_cnt)
    return 0;

  /* We compute the new length */
  off_t real_length = inode->data.length < offset + size ? offset + size : inode->data.length;

  while (size > 0) 
    {
      /* Sector to write, starting byte offset within sector. */
      disk_sector_t sector_idx = byte_to_sector (inode, offset);
      int sector_ofs = offset % DISK_SECTOR_SIZE;

      /* If needed we extend the file. It means that the sector_idx has not been initialized*/
      bool extend = sector_idx == (uint32_t)-1 && ok;
      if(extend){
	lock_acquire(&inode->read_write);
	int next_ind = offset / DISK_SECTOR_SIZE;
	lock_acquire(&inode->lock_idx);
	sector_idx = allocate_sector_in_index(inode, next_ind);
	lock_release(&inode->lock_idx);
      }

      /* Filling the gap it may result for offset*/
      off_t original_idx = inode_length (inode)/DISK_SECTOR_SIZE;
      off_t new_idx = offset / DISK_SECTOR_SIZE;
      while(original_idx + 1 < new_idx && ok){
	lock_acquire(&inode->lock_idx);
	disk_sector_t sec = allocate_sector_in_index(inode, original_idx + 1);
	lock_release(&inode->lock_idx);
	uint8_t *b = malloc(DISK_SECTOR_SIZE);
	if(b ==NULL)
	  PANIC("An error occurred in INODE_WRITE_AT trying to filling the gap between the file size and the extension");

	memset(b, 0, DISK_SECTOR_SIZE);
	disk_write (filesys_disk, sec, b);
	free(b);
	original_idx++;
      }	

      /* We set the new length if it's necessary */
      inode->data.length = inode->data.length < offset && ok ? offset : inode->data.length;

      /* Bytes left in inode, bytes left in sector, lesser of the two. */
      off_t inode_left = ok ? real_length - offset : inode_length (inode) - offset;
      int sector_left = DISK_SECTOR_SIZE - sector_ofs;
      int min_left = inode_left < sector_left ? inode_left : sector_left;

      /* Number of bytes to actually write into this sector. */
      int chunk_size = size < min_left ? size : min_left;

      /* We assure that the offset is less than inode's length*/
      if (chunk_size <= 0){
	if(extend)
	  lock_release(&inode->read_write);
        break;
      }

      if (sector_ofs == 0 && chunk_size == DISK_SECTOR_SIZE) 
        {
	  /* Write full sector directly to disk. */
          disk_write (filesys_disk, sector_idx, buffer + bytes_written); 
        }
      else 
        {
          /* We need a bounce buffer. */
          if (bounce == NULL) 
            {
              bounce = malloc (DISK_SECTOR_SIZE);
              if (bounce == NULL){
		if(extend)
		  lock_release(&inode->read_write);
                break;
	      }
            }

          /* If the sector contains data before or after the chunk
             we're writing, then we need to read in the sector
             first.  Otherwise we start with a sector of all zeros. */
          if (sector_ofs > 0 || chunk_size < sector_left) 
            disk_read (filesys_disk, sector_idx, bounce);
          else
            memset (bounce, 0, DISK_SECTOR_SIZE);
          memcpy (bounce + sector_ofs, buffer + bytes_written, chunk_size);
          disk_write (filesys_disk, sector_idx, bounce); 
        }

      /* Advance. */
      size -= chunk_size;
      offset += chunk_size;
      bytes_written += chunk_size;

      if(extend)
	lock_release(&inode->read_write);
    }

  inode->data.length =  (inode->data.length < offset + size) && ok ? offset+size : inode->data.length; //Therefore the file's lenght is now offset + size
  free (bounce);

  return bytes_written;
}

/* Disables writes to INODE.
   May be called at most once per inode opener. */
void
inode_deny_write (struct inode *inode) 
{
  inode->deny_write_cnt++;
  ASSERT (inode->deny_write_cnt <= inode->open_cnt);
}

/* Re-enables writes to INODE.
   Must be called once by each inode opener who has called
   inode_deny_write() on the inode, before closing the inode. */
void
inode_allow_write (struct inode *inode) 
{
  ASSERT (inode->deny_write_cnt > 0);
  ASSERT (inode->deny_write_cnt <= inode->open_cnt);
  inode->deny_write_cnt--;
}

/* Returns the length, in bytes, of INODE's data. */
off_t
inode_length (const struct inode *inode)
{
  return inode->data.length;
}

/* We get the sector stored at INDEX in INODE*/
static disk_sector_t get_sector_from_index(struct inode *inode, off_t index){
  if(index < 123)
    {//Then we just fetch what is in idx[index]
      return inode->data.idx[index];
    } 
  else if(index < 251)
    {
      if(inode->data.idx[123] == (uint32_t)-1)//First check that dix[123] is initialized
        return -1;
      
      if(inode->idx_cache[0] == NULL)
        {//Now make sure the first element in idx_cache is not null, if so retrieve indirect block from disk
          inode->idx_cache[0] = (struct indirect_b *)malloc(sizeof(struct indirect_b));
      
          if(inode->idx_cache[0] == NULL)
	          PANIC("Error allocating memory in GET_SECTOR_FROM_INDEX");
            
          disk_read(filesys_disk, inode->data.idx[123], (uint8_t *)inode->idx_cache[0]);//We fetch the indirect block at idx[123] in idx_cache[0]
        }
        
      return inode->idx_cache[0]->index[(index+5)%128];
    } 
  else if(index < 16635)
    {
    if(inode->data.idx[124] == (uint32_t)-1)//Is idx[124] initialized?
      return -1;
      
    //Then retrieve first double indirect block
    if(inode->idx_cache[1] == NULL){
      inode->idx_cache[1] = (struct indirect_b *)malloc(sizeof(struct indirect_b));
      
    if(inode->idx_cache[1] == NULL)
  	  PANIC("Error allocating memory in GET_SECTOR_FROM_INDEX");

      disk_read(filesys_disk, inode->data.idx[124], (uint8_t *)inode->idx_cache[1]);//We fetch the indirect block at idx[124] in idx_cache[1]
    }
    if(inode->idx_cache[1]->index[(index-251)/128] == (uint32_t)-1)
      return -1; //This is, when the index at the first double indirect block has not been initialized
    if(inode->idx_cache[((index-251)/128)+2] == NULL){//If the indirect block isn't in the idx_cache we set it there, in the right position
      inode->idx_cache[((index-251)/128)+2] = (struct indirect_b *)malloc(sizeof(struct indirect_b));
      if(inode->idx_cache[((index-251)/128)+2] == NULL)
	PANIC("Error allocating memory in GET_SECTOR_FROM_INDEX");
      
      disk_read(filesys_disk, inode->idx_cache[1]->index[(index-251)/128], (uint8_t *)inode->idx_cache[((index-251)/128)+2]);
    }
    return inode->idx_cache[((index-251)/128)+2]->index[(index-251)%128];
  } else {
    PANIC("Accessing out of range sector");
  }
}





/* We allocate a sector in disk to the given INDEX in INODE*/
static disk_sector_t allocate_sector_in_index(struct inode *inode, off_t index){
  if(index < 123){//The index is within the first 23 entries. Let's remember we have a total of 125 entries for sectors
    if(inode->data.idx[index] == (uint32_t)-1){ //If it has not been initialize
      inode->write_inode = true;//Thus we know the inode index has changed
      free_map_allocate(1, &inode->data.idx[index]);//We get a sector
      init_sector(inode->data.idx[index]);//Sector initialization
    }
    return inode->data.idx[index];
  } else if(index < 251){//If index E [123,251) we have an indirect block
    if(inode->data.idx[123] == (uint32_t)-1){//If the sector that points to the indirect block has not been initialized

      inode->write_inode = true;//Thus we know the inode index has changed
      
      struct indirect_b *new_indirect = (struct indirect_b *)malloc(sizeof(struct indirect_b));
      if(new_indirect == NULL)
	PANIC("Something wrong happened creating indirect block at ALLOCATE_SECTOR_IN_INDEX");

      init_indirect(new_indirect);//Indirect block initialization
      disk_sector_t sec;
      free_map_allocate(1, &sec);//The sector in disk where we are going to save the indirect block
      disk_write(filesys_disk, sec, (uint8_t *)new_indirect);//Write to disk
      inode->data.idx[123] = sec;// The sector that referes to the indirect block is now in the inode's index
      free(new_indirect);
    }
    if(inode->idx_cache[0] == NULL){//We start using our index cache. This will save us considerable disk access. The first element is the indirect block
      inode->idx_cache[0] = (struct indirect_b *)malloc(sizeof(struct indirect_b));
      if(inode->idx_cache[0] == NULL)
	PANIC("Error allocating space for idx_cache at ALLOCATE_SECTOR_IN_INDEX");

      disk_read(filesys_disk, inode->data.idx[123], (uint8_t *)inode->idx_cache[0]);//We fetch the indirect block at idx[123] in idx_cache[0]
    }
    if(inode->idx_cache[0]->index[(index+5)%128] == (uint32_t)-1){//If the corresponding index at the indirect block is not initialized
      inode->write[0] = true;//Thus we know the idx_cache[0] has changed
      
      free_map_allocate(1, &inode->idx_cache[0]->index[(index+5)%128]);//We get a sector
      init_sector(inode->idx_cache[0]->index[(index+5)%128]);// And initialize that sector
    }
    return inode->idx_cache[0]->index[(index+5)%128];
  } else if(index < 16635){
    if(inode->data.idx[124] == (uint32_t)-1){//If the double indirect block is not initialized

      inode->write_inode = true;//Thus we know the inode index has changed

      struct indirect_b *new_indirect = (struct indirect_b *)malloc(sizeof(struct indirect_b));

      if(new_indirect == NULL)
	PANIC("Something wrong happened creating indirect block at ALLOCATE_SECTOR_IN_INDEX");

      init_indirect(new_indirect);
      disk_sector_t sec;
      free_map_allocate(1, &sec);
      disk_write(filesys_disk, sec, (uint8_t *)new_indirect);
      inode->data.idx[124] = sec;
      free(new_indirect);
      //The first double indirect block is in disk at sec
    }
    if(inode->idx_cache[1] == NULL){//The second element in the index cache is the double indirect block
      inode->idx_cache[1] = (struct indirect_b *)malloc(sizeof(struct indirect_b));
      if(inode->idx_cache[1] == NULL)
	PANIC("Error allocating space for idx_cache at ALLOCATE_SECTOR_IN_INDEX");

      disk_read(filesys_disk, inode->data.idx[124], (uint8_t *)inode->idx_cache[1]);
    }
    if(inode->idx_cache[1]->index[(index-251)/128] == (uint32_t)-1){//We check that the indirect block in the indirect block is set

      inode->write[1] = true;//Thus we know the idx_cache[1] has changed

      struct indirect_b *new_indirect = (struct indirect_b *)malloc(sizeof(struct indirect_b));

      if(new_indirect == NULL)
	PANIC("Something wrong happened creating indirect block at ALLOCATE_SECTOR_IN_INDEX");

      init_indirect(new_indirect);
      disk_sector_t sec;
      free_map_allocate(1, &sec);
      disk_write(filesys_disk, sec, (uint8_t *)new_indirect);
      inode->idx_cache[1]->index[(index-251)/128] = sec;
      free(new_indirect);
    }
    if(inode->idx_cache[((index-251)/128)+2] == NULL){//If the indirect block isn't in the idx_cache we set it there, in the right position
      inode->idx_cache[((index-251)/128)+2] = (struct indirect_b *)malloc(sizeof(struct indirect_b));
      if(inode->idx_cache[((index-251)/128)+2] == NULL)
	PANIC("Error allocating space for idx_cache at ALLOCATE_SECTOR_IN_INDEX");
      
      disk_read(filesys_disk, inode->idx_cache[1]->index[(index-251)/128], (uint8_t *)inode->idx_cache[((index-251)/128)+2]);
    }
    if(inode->idx_cache[((index-251)/128)+2]->index[(index-251)%128] == (uint32_t)-1){//If the entry in the second double indirect block is not initialized

      inode->write[((index-251)/128)+2] = true;//Thus we know the idx_cache[((index-251)/128)+2] has changed      

      free_map_allocate(1, &inode->idx_cache[((index-251)/128)+2]->index[(index-251)%128]);
      init_sector(inode->idx_cache[((index-251)/128)+2]->index[(index-251)%128]);
    }
    return inode->idx_cache[((index-251)/128)+2]->index[(index-251)%128];
  } else {
    PANIC("Disk is full");
  }
}

/* This method initializes the SECTOR in disk as a zeroed chunk*/
static void init_sector(disk_sector_t sector){

  static char zeros[DISK_SECTOR_SIZE];
  disk_write(filesys_disk, sector, zeros);
}


/* This method initializes all 128 entries in IND_BLOCK as -1*/
static void init_indirect(struct indirect_b *ind_block){
  ASSERT (ind_block != NULL);

  int i;
  for(i=0; i<128; i++)
    ind_block->index[i] = -1;
}

